An AST is an ordered tree whose leaves are variables, and whose interior nodes are operators whose arguments are their children. An operator has an arity specifying how many arguments it takes, and what their sorts are.